package roteiro01;

public class QuickSortMedianThree {
	
	public int[] quickSort(int[] listaEntrada, int esquerda, int direita) {
		if (esquerda >= direita)
			return listaEntrada;
		
		int mediana = particiona(listaEntrada, esquerda, direita);
		quickSort(listaEntrada, esquerda, mediana-1);
		quickSort(listaEntrada, mediana+1, direita);
		return listaEntrada;
	} 	
	
	public int particiona(int[] listaEntrada, int esquerda, int direita) {
		
		int esquerdaParticiona = esquerda + 1;
		int direitaParticiona = direita;
		int pivot = listaEntrada[esquerda];
		
		while (esquerdaParticiona <= direitaParticiona ){
			if (listaEntrada[esquerdaParticiona] < pivot){
				esquerdaParticiona++;
			}
			else if ( pivot < listaEntrada[direitaParticiona]){
				direitaParticiona--;
			}
			else {
				swap(listaEntrada, esquerdaParticiona, direitaParticiona);
			}
			
		}
		swap(listaEntrada, esquerda, direitaParticiona);
		
		return direitaParticiona;	
	}
	
	public int[] quickSortMediaThree(int[] listaEntrada, int esquerda, int direita){
		particonaThree(listaEntrada, esquerda, direita);
		
		int esquerdaQuickSort = esquerda + 1;
		int direitaQuickSort = direita - 2;
		int pivot = listaEntrada[direita - 1];
		
		while (true){
			while (listaEntrada[esquerdaQuickSort] < pivot){
				esquerdaQuickSort++;
			}
			while (pivot < listaEntrada[direitaQuickSort]  ){
				direitaQuickSort--;				
			} if ( esquerdaQuickSort < direitaQuickSort ){
				swap(listaEntrada, esquerdaQuickSort, direitaQuickSort);
			} else {
				break;
			}	
		}
		
		swap(listaEntrada, esquerdaQuickSort, direita - 1);
		quickSort(listaEntrada, esquerdaQuickSort+1, direita);
		quickSort(listaEntrada, esquerda, esquerdaQuickSort-1);
		return listaEntrada;
		}

	private void particonaThree(int[] listaEntrada, int esquerda, int direita){
		int centro = (esquerda + direita)/2;
		if (listaEntrada[centro] < listaEntrada[esquerda] ){
			swap(listaEntrada, centro, esquerda);
		} 
		if (listaEntrada[direita] < listaEntrada[esquerda]){
			swap(listaEntrada, direita, esquerda);
		}
		if (listaEntrada[direita] < listaEntrada[centro]){
			swap(listaEntrada, direita, centro);
		}
		
		swap(listaEntrada, centro, direita-1);
	}
	
	private void swap(int[] listaEntrada, int i, int j){
		int indice = listaEntrada[i];
		listaEntrada[i] = listaEntrada[j];
		listaEntrada[j] = indice;
	}
}